// 买卖股票的最佳时机 IV
class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            int n = prices.size();
            k = min(k,n/2);
            vector<vector<int>> Hold(n,vector<int>(k+1)), DHold(n,vector<int>(k+1));
    
            Hold[0][0] = -prices[0];
            DHold[0][0] = 0;
            for(int i = 1; i <= k;i++)
            {
                Hold[0][i] = DHold[0][i]  = -0x3f3f3f;
            }
            for(int i = 1; i < n; i++)
            {
                Hold[i][0] = max(Hold[i-1][0],DHold[i-1][0] - prices[i]);
                for(int j = 1; j <= k; j++)
                {
                    Hold[i][j] = max(Hold[i-1][j],DHold[i-1][j] - prices[i]);
                    DHold[i][j] = max(DHold[i-1][j],Hold[i-1][j-1] + prices[i]);
                }
            }
            return *std::max_element(DHold[n - 1].begin(), DHold[n - 1].end());
        }
    };